package exam;

import javax.swing.*;
import java.util.Scanner;

public class day4 {


    public static void main3(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();
        int [][]arr=new int[n][n];

        for (int i = 0; i <n ; i++) {
            for (int j = 0; j <=i ; j++) {
             if(j==0||j==i){
                 arr[i][j]=1;
             }else {
                 arr[i][j]=arr[i-1][j]+arr[i-1][j-1];
             }
                System.out.printf("%5d",arr[i][j]);
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        String[]board={"XYZE","SFZS","XDEE"};
        String word="SEE";
        System.out.printf(exist(board,word)+"");
    }


    public static boolean exist (String[] board, String word) {
        int len=board[0].length();
        int high= board.length;
        for (int i = 0; i <high ; i++) {
            for (int j = 0; j <len ; j++) {
         int x=i;
         int y=j;
                if(board[i].charAt(j)==word.charAt(0)){
                    int [][]tmp=new int[high][len];
                    for (int k = 0; k <high ; k++) {
                        for (int l = 0; l <len ; l++) {
                            tmp[k][l]=0;
                        }
                    }
                    tmp[i][j]=1;
                   if (find(i,j,0,board,word,tmp))return true;
                }
            }
        }
        return false;
    }

    public static boolean find(int x,int y,int n,String[] board, String word,int [][]tmp){
        tmp[x][y]=1;
        if (n==word.length()-1&&board[x].charAt(y)==word.charAt(n)){
            return true;
        } else if (board[x].charAt(y)==word.charAt(n)) {
            boolean left=false;
            boolean right=false;
            boolean up = false;
            boolean down=false;
            if(y+1<board[x].length()&&tmp[x][y+1]!=1){
                left=find(x,y+1,n+1,board,word,tmp);
            }
            if (y-1>=0&&tmp[x][y-1]!=1){
                right=find(x,y-1,n+1,board,word,tmp);
            }
            if (x-1>=0&&tmp[x-1][y]!=1){
                up=find(x-1,y,n+1,board,word,tmp);
            }
            if (x+1<board.length&&tmp[x+1][y]!=1){
                down=find(x+1,y,n+1,board,word,tmp);
            }
            return right||left||up||down;
        }else {
            return false;
        }
    }





    public static void main1(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int x=scanner.nextInt();
        int l=0;
        int m=1;
        int r=1;

while(true){
if(x<=m+r&&x>=r){
    System.out.println(Math.min(m+r-x,x-r));
    return;
}
    int t=r+m;
    m=r;
    l=m;
    r=t;
}
    }
}
